import java.util.ArrayList;
import java.util.List;
// 力扣68. 文本左右对齐
class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        int k = 0;
        while (k < words.length) {
            int num = func(k, ans, words, maxWidth);
            k += num;
        }
        return ans;
    }

    public int func(int k, List<String> ans, String[] words, int maxWidth) {
        int num = 0; // 记录单词长度+最小空格数
        List<Integer> list = new ArrayList<>();
        int old = k;

        // 计算当前行能放多少个单词
        while (k < words.length) {
            int newLength = num + words[k].length();
            if (num > 0) newLength++; // 如果不是第一个单词，加一个空格
            if (newLength > maxWidth) break;

            list.add(k);
            num = newLength;
            k++;
        }

        StringBuilder res = new StringBuilder();
        int wordCount = list.size();
        // 计算需要分配的总空格数（减去单词间已有的最小空格）
        int totalSpaces = maxWidth - (num - (wordCount > 1 ? wordCount - 1 : 0));

        // 处理最后一行或只有一个单词的情况 - 左对齐
        if (wordCount == 1 || k == words.length) {
            for (int i = 0; i < wordCount; i++) {
                if (i > 0) res.append(" ");
                res.append(words[list.get(i)]);
            }
            // 在末尾补全空格
            while (res.length() < maxWidth) {
                res.append(" ");
            }
        } else {
            // 计算基础空格数和额外空格数
            // (wordCount - 1)为间隔数
            int baseSpaces = totalSpaces / (wordCount - 1);
            int extraSpaces = totalSpaces % (wordCount - 1);

            for (int i = 0; i < wordCount; i++) {
                res.append(words[list.get(i)]);
                if (i < wordCount - 1) { // 最后一个单词后不加空格
                    // 添加基础空格
                    for (int j = 0; j < baseSpaces; j++) {
                        res.append(" ");
                    }
                    // 如果有剩余空格，额外加一个
                    if (extraSpaces > 0) {
                        res.append(" ");
                        extraSpaces--;
                    }
                }
            }
        }

        ans.add(res.toString());
        return wordCount;
    }
}


// 力扣392. 判断子序列
class Solution1 {
    public boolean isSubsequence(String s, String t) {
        if(s.length()>t.length()){
            return false;
        }
        int l = 0;
        int r = 0;
        while(l<s.length() && r<t.length()){
            if(s.charAt(l) == t.charAt(r)){
                l++;
            }
            r++;
        }
        return (l==s.length())?true:false;
    }
}


// 力扣167. 两数之和 II - 输入有序数组
class Solution2 {
    public int[] twoSum(int[] numbers, int target) {
        for(int i=0;i<numbers.length;i++){
            int left = numbers[i];
            int right = target - numbers[i];
            int x = dichotomy(i+1,right,numbers);
            if(x!=-1){
                return new int[]{i+1,x+1};
            }
        }
        return new int[]{-1,-1};
    }
    public int dichotomy(int i,int target,int[] numbers){
        int left = i;
        int right = numbers.length-1;
        while(left<=right){
            int mid = left + (right-left)/2;
            if(numbers[mid] == target){
                return mid;
            }else if(numbers[mid] > target){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return -1;
    }
}